package com.cty.ninthDay;

import java.util.*;

/*
 *
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
 *
 *
 * */
public class Q_11 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 1, 2, 0, 5};
        int[] res = maxSlidingWindow4(nums, 3);
        System.out.println(Arrays.toString(res));
    }

    // 先找出最大值 记录他的索引值 如果在滑动窗口的里面 就选择 如果不在就重新选择
    // 这是主包自己写的太不容易了 时间复杂度O(nk) 空间复杂度O(n)
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < k) return new int[0];
        int max = Integer.MIN_VALUE, maxIndex = 0;
        // 记录当前最大值的索引和值
        HashMap<Integer, Integer> record = new HashMap<>();
        ArrayList<Object> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (nums[i] >= max) {
                max = nums[i];
                maxIndex = i;
            }
        }
        record.put(max, maxIndex);
        ans.add(max);
        //让滑动窗口移动
        for (int i = k; i < nums.length; i++) {
            if (record.get(max) < i - k + 1) {
                record.remove(max);
                max = Integer.MIN_VALUE;
                for (int j = i - k + 1; j <= i; j++) {
                    if (nums[j] >= max) {
                        max = nums[j];
                        maxIndex = j;
                    }
                }
                record.put(max, maxIndex);
                ans.add(max);
            } else if (nums[i] >= max) {
                max = nums[i];
                ans.add(max);
                record.put(max, i);
            } else {
                ans.add(max);
            }
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = (int) ans.get(i);
        }
        return res;
    }

    // 优先队列 时间复杂度O(nLogN) 力扣官方解题方法
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length < k) return null;
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        // 创建一个优先队列
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 判断里面的元素数组的第二个元素 也就是值 是否相等 相等则返回索引(元素数组中的第一个元素) 大的 不相等返回值比较大的
                return o1[1] != o2[1] ? o2[1] - o1[1] : o2[0] - o1[0];
            }
        });

        // 先把第一个窗口中的最大值计算出来
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{i, nums[i]});
        }
        // 插入到 结果数组
        ans[0] = pq.peek()[1];
        // 开始遍历剩下的值
        for (int i = k; i < n; i++) {
            pq.offer(new int[]{i, nums[i]});
            // 判断栈顶元素是否还在队列中
            while (pq.peek()[0] <= i - k) {//不在就持续出栈 因为是优先队列所以在栈顶的永远是最大值的元素
                pq.poll();
            }
            //将本次最大的值加入结果数组
            ans[i - k + 1] = pq.peek()[1];
        }
        return ans;
    }


    // 单调队列(力扣官方题解)
    public static int[] maxSlidingWindow3(int[] nums, int k) {
        if (nums.length < k) return null;
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        //创建一个双向链表
        LinkedList<Integer> indexs = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            // 判断双端链表的末端是否比当前元素小 是就直接移除加入新的元素 保证链表中的第一个元素为最大值
            while (!indexs.isEmpty() && nums[i] >= nums[indexs.peekLast()]) {
                indexs.pollLast();
            }
            indexs.offerLast(i);
        }
        ans[0] = nums[indexs.peekFirst()];
        for (int i = k; i < n; i++) {
            // 先进行末尾比较
            while (!indexs.isEmpty() && nums[i] >= nums[indexs.peekLast()]) {
                indexs.pollLast();
            }
            indexs.offerLast(i);
            // 再判断最前面的最大值是否 已经不在窗口中
            while (indexs.peekFirst() <= i - k) {
                indexs.pollFirst();
            }
            ans[i - k + 1] = nums[indexs.peekFirst()];
        }
        return ans;
    }


    //分块 + 预处理 （力扣官方题解） 时间复杂度O(n)
    public static int[] maxSlidingWindow4(int[] nums, int k) {
        if (nums.length < k) return null;
        int n = nums.length;
        int[] ans = new int[n - k + 1], prefixMax = new int[n], suffixMax = new int[n];
        // 存储前缀的最大值
        for (int i = 0; i < n; i++) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            } else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
        // 存储后缀的最大值
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        for (int i = 0; i <= n - k; i++) {
            ans[i] = Math.max(prefixMax[i + k - 1], suffixMax[i]);
        }
        return ans;
    }

}
